#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include "heap.h"

#define RUN_TEST(t) { if(t()) cout << #t << " OK" << endl; else cout << #t << " FAIL" << endl; }

#define DEBUG(X)

using namespace std;

Heap heap;

vector<pair<int, int> > toInsert;


struct insert_params
{
	Heap h;
	int start, end, step;
};


void* insertElements(void *pp)
{
	insert_params *p = (insert_params *)pp;
	Heap h = p->h;
	int start = p->start;
	int end = p->end;
	int step = p->step;
	for(int i = start; i < end; i+= step)
		Heap_Insert(h, i, i*3);
}



bool testAllSerial()
{
	Heap h = Heap_Create(1);

	insert_params p;
	p.h = h;
	p.start = 17;
	p.end = 340;
	p.step = 3;

	insertElements(&p);

	multiset<int> expected, actual;
	for(int i = p.start; i < p.end; i+= p.step)
		expected.insert(i*3);
	
	bool isFirst = true;
	int previousPrio = -1;
	while(1)
	{
		int error = 0;
		int priority;
		int x = Heap_Pop(h, &error, &priority);
		if(error)
			break;
		actual.insert(x);
		
		
		if(isFirst)
		{
			isFirst = false;
			previousPrio = priority;
		}
		else
		{
			if(priority < previousPrio)
			{
				Heap_Delete(h);
				return false;
			}
			previousPrio = priority;
		}
	}
	Heap_Delete(h);

	return expected == actual;
}


bool testParallelInsertSerialPop()
{
	Heap h = Heap_Create(1);

	multiset<int> expected, actual;
	insert_params params[8];
	pthread_t t[8];
	for(int i = 0; i < 8; i++)
	{
		params[i].h = h;
		params[i].start = i*45+170;
		params[i].end = i*52+325;
		params[i].step = (i+4)/3;
		for(int j = params[i].start; j < params[i].end; j += params[i].step)
			expected.insert(j*3);
	}


	for(int i = 0; i < 8; i++)
	{
		pthread_create(&t[i],NULL, insertElements, &params[i]);
	}

	for(int i = 0; i < 8; i++)
		pthread_join(t[i],NULL);

	bool isFirst = true;
	int previousPrio = -1;
	while(1)
	{
		int error = 0;
		int priority;
		int x = Heap_Pop(h, &error, &priority);
		if(error)
			break;
		actual.insert(x);
			
		if(isFirst)
		{
			isFirst = false;
			previousPrio = priority;
		}
		else
		{
			if(priority < previousPrio)
			{
				Heap_Delete(h);
				return false;
			}
			previousPrio = priority;
		}
	}
	Heap_Delete(h);
	return expected == actual;
}

void* insertVector(void* pair_indexes)
{
	pair<int,int>  p = *(pair<int,int>*) pair_indexes;

	int start = p.first;
	int stop = p.second;

	DEBUG(printf("thread %d: start = %d, stop = %d\n",pthread_self()%1000, start, stop);)
	for(int i = start; i < stop; i++)
	{
		DEBUG(printf("thread %d: w -> %d\n", pthread_self()%1000, i);)
		//printf("thread %d: w -> %d\n", pthread_self()%1000, i);
		Heap_Insert(heap, toInsert[i].first, toInsert[i].second);
		// printf("%d - %d ; expected\n",toInsert[i].first, toInsert[i].second);
	}
}

void* popElements(void* int_numOfPop)
{
	int numofPops = *(int*) int_numOfPop;
	vector<pair<int, int> > *elements = new vector<pair<int, int> >(numofPops, make_pair(-171,-172));

	//printf("thread %d: numofPops -> %d\n", pthread_self()%1000, numofPops);
	for(int i = 0; i < numofPops; i++)
	{
		DEBUG(printf("thread %d: r -> %d\n", pthread_self()%1000, i);)
		int isError = 0;
		do{
			DEBUG(printf("thread %d: looping pop, r -> i\n", pthread_self()%1000, i);)
			(*elements)[i].second = Heap_Pop(heap, &isError, &((*elements)[i].first));
		}while(isError == 1);
		// printf("%d - %d ; actual\n",(*elements)[i].first, (*elements)[i].second);
	}
	pthread_exit(elements);
}

bool testParallelInsertParallelPop()
{
	int numOfThreads = 8;
	int numOfOps = 1000;
	srand(time(0));
	int totalElements = numOfThreads * numOfOps;

	heap = Heap_Create(1); //sometimes, doubling the size of the heap doesn't work so this test don't do it: the heap size is enough big
	
	toInsert.resize(totalElements);
	for(int i = 0; i < totalElements; i++)
	{
		toInsert[i].first = rand() - rand();
		toInsert[i].second = rand() - rand();
	}
	vector<pair<int, int> > inputs(numOfThreads);
	for(int i = 0; i < numOfThreads; i++)
		inputs[i] = make_pair(i*numOfOps, (i+1)*numOfOps);

	vector<pthread_t> t_w(numOfThreads), t_r(numOfThreads);

	for(int i = 0; i < numOfThreads; i++)
	{
		pthread_create(&t_w[i], NULL, insertVector, &inputs[i]);
		pthread_create(&t_r[i], NULL, popElements, &numOfOps);
	}
	
	vector< vector<pair<int, int> >* > outputs(numOfThreads);
	for(int i = 0; i < numOfThreads; i++)
	{
		pthread_join(t_w[i], NULL);
		pthread_join(t_r[i], (void**)&outputs[i]);
	}
	Heap_Delete(heap);
	
	multiset<pair<int, int> > expected, actual;
	for(int i =  0; i < toInsert.size(); ++i)
	{	
		expected.insert(toInsert[i]);
	}
	for(int i =  0; i < outputs.size(); ++i)
	{
		for(int j = 0 ; j < outputs[i]->size(); ++j)
		{
			actual.insert((*outputs[i])[j]);
		}
	}
	
	for(int i = 0; i < numOfThreads; i ++)
	{
		delete outputs[i];
	}
	return expected == actual;
}

bool testSerialInsertParallelPop()
{
	int numOfThreads =8;
	int numOfOps = 1000;
	int totalElements = numOfThreads*numOfOps;
	srand(time(0));
	heap = Heap_Create(1);
	toInsert.resize(totalElements);
	for(int i = 0; i < totalElements; i++)
	{
		toInsert[i].first = rand() % 1000000;
		toInsert[i].second = rand() % 1000000;
		Heap_Insert(heap,toInsert[i].first,toInsert[i].second);
	}
	
	vector<pthread_t> t_r(numOfThreads);
	for(int i = 0; i < numOfThreads; i++)
	{
	   pthread_create(&t_r[i], NULL, popElements, &numOfOps);
	}
	
	vector<vector<pair<int, int> >* > outputs(numOfThreads);
	for(int i = 0; i < numOfThreads; i++)
	{
		pthread_join(t_r[i], (void**)&outputs[i]);
	}
	Heap_Delete(heap);
	int A = 0, B = 0;
	for(int i=0; i<outputs.size(); i++)
	{
		bool isFirst = true;
		int previousPrio = -1;
		for(int j = 0 ; j < outputs[i]->size(); j++)
		{
			A++;
			int priority = (*outputs[i])[j].first;
			if(isFirst)
				isFirst = false;
			else if(priority < previousPrio)
			{
				DEBUG(printf(" j = %d, priority = %d, previousPrio = %d\n",j, priority, previousPrio);)
				B++;
			}
			previousPrio = priority;
			
		}
	}
	
	if(B > 0)
	{
		DEBUG(printf("ERRORS: %d / %d\n", B, A);)
		return false;
	}
	
	
	multiset<pair<int, int> > expected, actual;
	for(int i =  0; i < toInsert.size(); ++i)
	{
		expected.insert(toInsert[i]);
	}
	
	for(int i =  0; i < outputs.size(); ++i)
	{
		for(int j = 0 ; j < outputs[i]->size(); ++j)
		{
			actual.insert((*outputs[i])[j]);
		}
	}
	
	for(int i = 0; i < numOfThreads; i ++)
	{
		delete outputs[i];
	}
	return expected == actual;
}

int main()
{
 	RUN_TEST(testAllSerial);
	RUN_TEST(testParallelInsertSerialPop);
	RUN_TEST(testParallelInsertParallelPop);
	RUN_TEST(testSerialInsertParallelPop);
	return 0;
}
